package algorithms;

import java.util.Set;

public class Problem139 {
	public boolean wordBreak(String s, Set<String> dict) {
		if (s == null || "".equals(s))
			return false;
		int[] dp = new int[s.length()];
		for (int i = 0; i < s.length(); i++) {
			if (dict.contains(s.substring(0, i + 1)))
				dp[i] = 1;
			else {
				for (int j = 0; j < i; j++) {
					if (dp[j] == 1 && dict.contains(s.substring(j + 1, i + 1))) {
						dp[i] = 1;
						break;
					}
				}
			}
		}
		return dp[s.length() - 1] == 0;
	}
}
